

import java.awt.Point;
import java.util.ArrayList;
import java.util.Random;

/**
 * Generator class is used to create puzzle automatically.
 */

public class Generator {

	// Difficulty levels:
	public static final int LEVEL_EASY 		= 0;
	public static final int LEVEL_NORMAL 	= 1;
	public static final int LEVEL_HARD 		= 2;
	public static final int LEVEL_VERY_HARD = 3;
	public int difficulty;

	// the grid with the numbers
	private int[][] grid;
	// random and array list
	private Random ran;
	private ArrayList<Integer> al;
	// number of row and column in a region
	private int size;
	private int regionSize;

    // the given numbers:
    public int[][] given;
    private int countGiven;
    private boolean option;
    private static int diff_conunt = 0;
    

    
    //Constructor
    Generator(boolean _option) {
    	this.size = 3;
		regionSize = size;
		this.size = size * size;
        this.grid  = new int[this.size][this.size];
        this.given = new int[this.size][this.size];
		// random number generator
		ran = new Random();
		// arraylist that will contain the possible values for every case in the grid
		al = new ArrayList<Integer>();
		// Symmetrical option in Setting Game feature
		this.option =  _option;
    }
	    
    public boolean createSudoku() {
    	
    	// initial value
        this.difficulty = 0;
        //call generate method for creating the puzzle grid with all correct number in each position
    	this.generate(false);

		countGiven = 0;
		difficulty = 0;
		//while(difficulty == 0) {
			
	        // Select 30 random numbers to show
	        this.randomGiven(30);
            difficulty = this.solvable(this.given);
	        
	        // Keep adding numbers until the puzzle is solvable
	        while(difficulty == 0 && countGiven < 37) {
	        	this.addRandomGiven();
	            difficulty = this.solvable(this.given);
	        }
		//}//while
		if(difficulty == 0){
			// can not find the solvable puzzle
			return false;
		}else{
			// find the solvable puzzle
			return true;
		}
    }//createSudoku()

    /** Creating puzzle grid with all correct number in each position*/
    public void generate(boolean traceOn) {
    	// start by row 0
    	int currentRow = 0;
    	// to count the startOver
    	int[] trials = new int[size];
		// now let's fill the grid row by row
		while(currentRow < size) {
			trials[currentRow]++;
			// try to generate the row if it works pass to next roow
			if(genRow(currentRow)) {
				if(traceOn) {
					System.out.print("Row " + (currentRow+1) + " generated after " + trials[currentRow] + " trial");
					if(trials[currentRow] > 1)
						System.out.print("s");
					System.out.println(".");
				}
				currentRow++;
				continue;
			}
			// so it didn't work check our count
			if(trials[currentRow] < regionSize * regionSize * regionSize * 2) {
				continue;
			}
			// so despite all our effort it does not fit we will have to restart for the whole
			// row regions
			if(traceOn) 
				System.out.print("Quitting for row: " + (currentRow+1));
			while(currentRow % regionSize != 0) {
				trials[currentRow--] = 0;
			}
			trials[currentRow] = 0;
			if(traceOn)
				System.out.println(". Starting over with row: "  + (currentRow+1) + ".");
		}
		// ok our grid is filled with 0-size but sudoku grids do not have 0
		for(int i = 0; i < size; i++) {
			for(int j = 0; j < size; j++) {
				grid[i][j]++;
			}
		}
    }

    // try to generate an return true if it worked
    // (it might be impossible to fill the row for example if the only element left in the row
    // is 5 so the last column must be 5 but I may already have a 5 in the column or region)
    private boolean genRow(int row) {
    	// for every column in the row
    	for(int col = 0; col < size; col++) {
    		// fill the arrayList of available value if no value abort
    		if(fillArrayList(row, col) == 0) {
    			return false;
    		}
    		// retrieve a random value from the arrayList
    		grid[row][col] = al.remove(ran.nextInt(al.size()));
    	}
    	return true;
    }
	// fill the ArrayList with all available number for that row,col
	// returns the number of elements in the arraylist
	private int fillArrayList(int row, int col) {
		boolean[] available = new boolean[size];
		// flag all the slot as available
		for(int i = 0; i < size; i++)
			available[i] = true;
		
		// remove the number already used in row
		for(int i = 0; i < row; i++)
			available[grid[i][col]] = false;
		// remove the number already used in col
		for(int i = 0; i < col; i++)
			available[grid[row][i]] = false;
		// now the region. I just have to take care of the row over me in
		// the region the columns to the left of my position have already been checked as unavailable
		Point rowRange = getRegionRowsOrCols(row);
		Point colRange = getRegionRowsOrCols(col);
		for(int i = rowRange.x; i < row; i++) {
			for(int j = colRange.x; j <= colRange.y; j++) {
				available[grid[i][j]] = false;
			}
		}
		
		// empty the arrayList
		al.clear();
		// fill it with all still available numbers
		for(int i = 0; i < size; i++) {
			if(available[i])
				al.add(i);
		}
		return al.size();
	}
    // return the first and last row/column of the region into which is located the (row or col)
    private Point getRegionRowsOrCols(int rowOrCol) {
    	int x = (rowOrCol / regionSize) * regionSize;
    	int y = x + regionSize - 1;
    	Point point = new Point(x,y);
    	return point;
    }
	
	// to retrieve the grid
	public int[][] getGrid() {
		return this.grid;
	}

    // randomGiven(x) means: exactly x numbers are shown.
    // The lower this number, the more difficult the puzzle.
    // At least 30 numbers need to be shown for any puzzle to be solvable.
    private void randomGiven(int showHowMany) {
        // Erase all given numbers, of previous tries.
        for(int i=0; i<this.size; i++) {
            for(int j=0; j<this.size; j++) {
                this.given[i][j] = 0;
            }
        }
        while(countGiven < showHowMany)
        	this.addRandomGiven();
    }
    
    /** add one more number to the creating grid*/
    private void addRandomGiven() {
        int i = (int) (Math.random() * this.size);
		int j = (int) (Math.random() * this.size);
    	while(this.given[i][j] != 0) {
            i = (int) (Math.random() * this.size);
			j = (int) (Math.random() * this.size);
    	}
    	
    	this.given[i][j] = this.grid[i][j];
    	countGiven++;
    	
		// If you make the puzzles symmetrical, they are generally easier,
		// but much better looking :)
    	if(option) {
	    	this.given[j][this.size-i-1] = this.grid[j][this.size-i-1];
	    	this.given[this.size-i-1][this.size-j-1] = this.grid[this.size-i-1][this.size-j-1];
	    	this.given[this.size-j-1][i] = this.grid[this.size-j-1][i];
	    	this.given[j][i] = this.grid[j][i];
	    	this.given[i][this.size-j-1] = this.grid[i][this.size-j-1];
	    	this.given[this.size-i-1][j] = this.grid[this.size-i-1][j];
	    	this.given[this.size-j-1][this.size-i-1] = this.grid[this.size-j-1][this.size-i-1];
	    	this.countGiven += 7;
    	}
    	
    }
    
    /** check if the generated puzzle is solvable */
    private int solvable(int[][] g) {
    	// returns difficulty if puzzle is solvable, or 0 otherwise
    	int[][] _puz = new int[this.size][this.size];
    	for(int i=0; i<this.size; i++) {
            for(int j=0; j<this.size; j++) {
            	_puz[i][j] = g[i][j];
            }
        }
    	return solve(0,0,_puz);   
    }
    
    /** solve the puzzle using backtracking algorithm like N-Queen puzzle*/
    // return the number of time of backtrack for calculate the level of difficulty
    static int solve(int i, int j, int[][] cells) {
        if (i == 9) {
            i = 0;
            if (++j == 9)
                return diff_conunt;
        }
        
        if (cells[i][j] != 0)  // skip filled cells
            return solve(i+1,j,cells);

        for (int val = 1; val <= 9; ++val) {
            if (legal(i,j,val,cells)) {
                cells[i][j] = val;
                diff_conunt++;
                if (solve(i+1,j,cells) != 0)
                    return diff_conunt;
            }
        }
        cells[i][j] = 0; // reset on backtrack
        return 0;
    }
    
    /** check violation of the number on the grid position */
    static boolean legal(int i, int j, int val, int[][] cells) {
        for (int k = 0; k < 9; ++k)  // check on row
            if (val == cells[k][j])
                return false;

        for (int k = 0; k < 9; ++k) // check on column
            if (val == cells[i][k])
                return false;

        int boxRowOffset = (i / 3)*3;
        int boxColOffset = (j / 3)*3;
        for (int k = 0; k < 3; ++k) // box
            for (int m = 0; m < 3; ++m)
                if (val == cells[boxRowOffset+k][boxColOffset+m])
                    return false;

        return true; // no violations, so it's legal
    }
 
    // Returns the difficulty level (1...4) based on the difficulty points from 
    // the number of time of backtrack in solving puzzle
   
    public int getDifficultyLevel() {
    	if(this.difficulty<8600)
    		return LEVEL_EASY;
    	if(this.difficulty<25000)
    		return LEVEL_NORMAL;
    	if(this.difficulty<75000)
    		return LEVEL_HARD;
		return LEVEL_VERY_HARD;
    }
    
    public int[] getPuzzle(){
    	int[] p = convertPuzzle(fromPuzzle2Puzzle1(this.given));
    	return p;
    }
    
    public int[] getSolution(){
    	int[] s =convertPuzzle(fromPuzzle2Puzzle1(this.getGrid()));
    	return s;
    }
    
    private int[] fromPuzzle2Puzzle1(int[][] o_puzzle) {
		int[] puz = new int[9 * 9];
		int cell = 0;
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				puz[cell] = o_puzzle[i][j];
				cell++;
			}
		}
		return puz;
	}
	
	// convert 
	private int[] convertPuzzle(int[] p){
		int[] puz = new int[9 * 9];
		int[] d = new int[9];
		d[0]=0;
		d[1]=1;
		d[2]=2;
		d[3]=9;
		d[4]=10;
		d[5]=11;
		d[6]=18;
		d[7]=19;
		d[8]=20;
		int cell = 0;
		for(int i=0;i<3;i++){
			for (int j=0;j<3;j++){
				for (int k=0;k<9;k++){
					puz[cell]= p[d[k]+(j*3)+(i*27)];
					cell++;
				}
			}
		}
		
		return puz;
	}
    
}